package cn.edu.cqvie.atc.sort.impl;

import cn.edu.cqvie.atc.sort.Sort;

import java.util.Comparator;

/**
 * 快速排序
 *
 * @author Zheng Shaohong
 */
public class QuickSort <T> extends BaseSort<T> {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{23, 12, 8, 0, 18, 90, 1, 2, 3, 22};

//        long[] arr = new long[10];
//        for (int i = 0; i < 10; i++) {
//            arr[i] = (long) (Math.random() * 100);
//        }

        Sort<Integer> s = new QuickSort<Integer>();
        s.display(arr);
        s.sort(arr,  new IntegerComparator());
        s.display(arr);

    }


    public void sort(T[] arr, int left, int right) {
        if (right - left <= 0) {
            return;
        } else {
            // 设置关键字
            T point = arr[right];
            // 获取的切入点，同时对数组进行划分
            int partition = partition(arr, left, right, point);
            // 对左边的子数组进行快速排序
            sort(arr, left, partition - 1);
            sort(arr, partition + 1, right);
        }

    }

    /**
     * 划分数组
     */
    public int partition(T[] arr, int left, int right, T point) {
        int leftPtr = left - 1;
        int rightPtr = right;
        while (true) {

            // 循环，将比关键字小的留在左端
            while (leftPtr < rightPtr && c.compare(arr[++leftPtr], point) < 0) {
            }

            // 循环，将比关键字大的留在右端
            while (rightPtr > leftPtr && c.compare(arr[--rightPtr], point) > 0) {
            }

            if (leftPtr >= rightPtr) {
                break;
            } else {
                T tmp = arr[leftPtr];
                arr[leftPtr] = arr[rightPtr];
                arr[rightPtr] = tmp;
            }
        }
        // 将关键字和当前leftPtr所指的这个一个进行交换
        T tmp = arr[leftPtr];
        arr[leftPtr] = arr[right];
        arr[right] = tmp;
        return leftPtr;
    }

    @Override
    public void sort(T[] arr, Comparator<T> c) {
        this.c = c;
        sort(arr, 0, arr.length -1);
    }
}
